import java.util.Stack;

public class Test21 {
    public static class StackWithMin<T extends Comparable<T>>{
        private Stack<T> dataStack;
        private Stack<T> minStack;

        public StackWithMin() {
            dataStack = new Stack<>();
            minStack = new Stack<>();
        }

        public T pop(){
            if (dataStack.isEmpty()){
                throw new RuntimeException("IS Empty");
            }
            // 如果有数据，最小数位置栈和数据栈必定是有相同的元素个数，
            // 两个栈同时出栈
            minStack.pop();
            return dataStack.pop();
        }

        public void push(T t){
            if (t == null) throw new RuntimeException("can not be null");
            if(dataStack.isEmpty()){
                dataStack.push(t);
                minStack.push(t);
            }else{
                dataStack.push(t);
                T temp = minStack.peek();
                if(temp.compareTo(t) > 0){
                    minStack.push(t);
                    // 插入的元素不比原来的最小元素小，复制最小栈栈顶元素，将其入栈
                }else minStack.push(minStack.peek());
            }
        }

        public T min(){
            if (minStack.isEmpty()) throw new RuntimeException("No element in stack.");
            return minStack.peek();
        }
    }
    public static void main(String[] args) {
        StackWithMin<Integer> stack = new StackWithMin<>();
        stack.push(3);
        System.out.println(stack.min());
        stack.push(4);
        System.out.println(stack.min());
        stack.push(2);
        System.out.println(stack.min());
        stack.push(3);
        System.out.println(stack.min());
        stack.pop();
        System.out.println(stack.min());
        stack.pop();
        System.out.println(stack.min());
        stack.push(0);
        System.out.println(stack.min());
    }
}
